package com.insertSort;

import com.Sort;

/**
 * 插入排序
 *
 * @param <Item>
 */
public class InsertionSort<Item extends Comparable<Item>> extends Sort<Item> {

    public void sort(Item[] comparableArray) {
//        unSortStartIndex：数组中未排序的起始索引
        for (int unSortStartIndex = 0; unSortStartIndex < comparableArray.length; unSortStartIndex++) {
//          sortedIndex：数组中已排序的索引
            for (int sortedIndex = 0; sortedIndex < unSortStartIndex; sortedIndex++) {
//                未排序的item比已经排好序的item要小，那么说明这个item应该放在已排序的这个位置
                if (super.less(comparableArray[unSortStartIndex], comparableArray[sortedIndex])) {
//                    保存将要插入到已排序的数组中的项，因为后面整体移动的时候会覆盖这个要移动的项
                    Item temp = comparableArray[unSortStartIndex];
//                    要插入到有序数组的index到未排序index之间的元素整体往后移动，腾出空位，方便后续插入
                    System.arraycopy(comparableArray, sortedIndex, comparableArray, sortedIndex + 1, unSortStartIndex - sortedIndex);
//                   执行插入
                    comparableArray[sortedIndex] = temp;
                }
            }

        }
    }
}
